package cn.kuick.match3.test1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class RemoveDuplicateLetters {

	
	public static void innerOutput(int i, List<String> keys, Map<String, ArrayList<Integer>> statResult, char[] buf, StringBuffer minResult) {
		String key = keys.get(i);
		ArrayList<Integer> values = statResult.get(key);
		
		for(int j=0; j<values.size(); j++) {
			int index = values.get(j);
			buf[index] = key.charAt(0);
			
			if (i < keys.size() - 1) {
				innerOutput(i + 1, keys, statResult, buf, minResult);
			} else {
				findMin(buf, minResult);
			}
			
			buf[index] = '\0';
		}
	}
	
	public static String StringMin(String str1, String str2) {
		if (str1.compareTo(str2) > 0) {
			return str2;
		} else {
			return str1;
		}
	}
	
	public static void findMin(char[] buf, StringBuffer minResult) {
		 StringBuffer sb = new StringBuffer();
		 
		 for(int i=0;i<buf.length; i++) {
			 char ch = buf[i];
			 
			 if (ch != '\0') {
				 sb.append(ch);
			 }
		 }
		 
		 String min = StringMin(sb.toString(), minResult.toString());
		 
		 minResult.setLength(0);
		 minResult.append(min);
	}
	
	public static void statistics(String target, Map<String, ArrayList<Integer>> statResult) {
		for(int i=0; i<target.length(); i++) {
			char ch = target.charAt(i);
			ArrayList<Integer> arrays = statResult.get(String.valueOf(ch));
			
			if (arrays == null) {
				arrays = new ArrayList<Integer>(target.length());
				statResult.put(String.valueOf(ch), arrays);
			}
			
			arrays.add(i);
		}
	}
	
	public static String handle(String target) {
		StringBuffer minResult = new StringBuffer(target);
		
		Map<String, ArrayList<Integer>> statResult = new LinkedHashMap<String, ArrayList<Integer>>();
		statistics(target, statResult);
		
		char[] buf = new char[target.length()];
		
		for(int i=0; i<buf.length;i++) {
			buf[i] = '\0';
		}
		
		List<String> keys = new ArrayList<String>();
		for(Iterator<String> it=statResult.keySet().iterator(); it.hasNext();) {
			keys.add(it.next());
		}
		
		innerOutput(0, keys, statResult, buf, minResult);
		
		return minResult.toString();
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(handle("ccaecbbdda"));
		System.out.println(handle("ddcaaffecbbb"));
	}

}
